package leetcode.D800.T787;

import java.util.*;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-23 20:37:24 星期三
 */
class Solution {
    // 一刷，通过率41 / 49 ，最后是copy别人解法过的，下面是自己写的，懒得改了，放弃！
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<flights.length; ++i) {
            if (map.containsKey(flights[i][0]))
                map.get(flights[i][0]).add(i);
            else {
                List<Integer> list = new LinkedList<>();
                list.add(i);
                map.put(flights[i][0], list);
            }
        }
        Map<Integer, Integer>[] dp = new Map[n];
        dp[src] = new HashMap<>();
        dp[src].put(0, 0);
        Deque<Integer> queue = new LinkedList<>();
        boolean[] queued = new boolean[n];
        queue.addLast(src);
        int range = 0;
        while(!queue.isEmpty()) {
            if (range > k)
                break;
            int size = queue.size();
            for(int i=0; i<size; ++i) {
                int front = queue.removeFirst();
                if (!map.containsKey(front))
                    continue;
                List<Integer> idxs = map.get(front);
                Iterator<Integer> iterator = idxs.iterator();
                while (iterator.hasNext()) {
                    int idx = iterator.next();
                    int end = flights[idx][1], cost = flights[idx][2];
                    if (dp[end] == null)
                        dp[end] = new HashMap<>();
                    for (Map.Entry<Integer, Integer> entry : dp[front].entrySet()) {
                        if (entry.getKey() <= range) {
                            Integer total = dp[end].getOrDefault(entry.getKey()+1, Integer.MAX_VALUE);
                            dp[end].put(entry.getKey()+1, Math.min(total, entry.getValue()+cost));
                        }
                    }
                    if (!queued[end]) {
                        queued[end] = true;
                        queue.addLast(end);
                    }
                }
            }
            range++;
        }
        if (dp[dst] == null)
            return -1;
        int result = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : dp[dst].entrySet()) {
            if (entry.getKey() <= (k+1))
                result = Math.min(result, entry.getValue());
        }
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}
